class Solution {

public:

    int minDistance(string word1, string word2) {

        int n=word1.size(),m=word2.size();
        vector<vector<int>> vecDp(n+1,vector<int>(m+1));
        for(int i=0;i<m;++i){
            vecDp[0][i+1]=i+1;
        }
        for(int i=0;i<n;++i){
            vecDp[i+1][0]=i+1;
            for(int j=0;j<m;++j){
                vecDp[i+1][j+1]=word1[i]==word2[j]?vecDp[i][j]
                :min(vecDp[i][j+1],min(vecDp[i][j],vecDp[i+1][j]))+1;
            }
        }
        
        return vecDp[n][m];
    }
};

